package com.cuz.hot100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Q51solveNQueens {
    public static void main(String[] args) {
//        System.out.println(solveNQueens1(1));
        System.out.println(solveNQueens1(4));
    }

    public static List<List<String>> solveNQueens1(int n) {
        List<List<String>> res = new ArrayList<>();
        for (int col = 0; col < n; col++) {
            int[] memory = new int[n];
            memory[0] = col;
            LinkedList<String> tempRes = new LinkedList<>();
            tempRes.add(generateQueueStr(col, n));
            process(memory, n, 1, res, tempRes);
        }
        return res;
    }

    /**
     * 回溯
     *
     * @param memory  第index行放在了memory[index]列
     * @param n       总共多少个皇后
     * @param curRow  当前第几行 从0开始
     * @param res     结果
     * @param tempRes 临时结果
     */
    private static void process(int[] memory, int n, int curRow, List<List<String>> res, LinkedList<String> tempRes) {
        if (curRow == n ) {
            res.add(new ArrayList<>(tempRes));
            return;
        }
        for (int colToSave = 0; colToSave < n; colToSave++) {
            if (isValid(curRow, colToSave, memory)) {
                memory[curRow] = colToSave;
                tempRes.addLast(generateQueueStr(colToSave, n));
                process(memory, n, curRow + 1, res, tempRes);
                memory[curRow] = 0;
                tempRes.removeLast();
            }
        }
    }

    private static String generateQueueStr(int col, int n) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i == col) {
                res.append("Q79WordsSearch");
            } else {
                res.append(".");
            }
        }
        return res.toString();
    }

    private static boolean isValid(int x, int y, int[] memory) {
        for (int row = 0; row < x; row++) {
            int col = memory[row];
            if (col == y) {
                return false;
            }
            if (Math.abs(row - x) == Math.abs(col - y)) {
                return false;
            }
        }
        return true;
    }
}
